The present invention relates to a method and apparatus for division in data processing system and specially for floating point division in radix-2.sup.n digital computer where n&gt;1.
Division by iterative multiplications has been implemented in the division process of digital computer. One technique described in "The IBM System/360 Model 91: Floating-point Execution Unit" IBM Journal of Res. & Develop. Vol. 11 No. 1, 1967 pp. 34-54 by S. F. Anderson et al. treats the dividend and divisor as numerator and denominator of a fraction. It accomplishes the division by multiplying both the numerator and denominator with the same sequence of convergence factors until the denominator approaches approximately unity. The resulting numerator then is considered an approximated quotient.
It is assumed the dividend and divisor are positive and normalized fractions in floating point number representation with the range 1&gt;A,B.gtoreq.1/D where D denotes a radix. This normalized range implies that the divisor can be expressed as B=1-q for some q in the range 0&lt;q.ltoreq.(D-1)/D. The first multiplying factor is chosen as R.sub.o =1+q then B.sub.o =B.times.R.sub.o =(1-q)(1+q)=1-q.sup.2. The second multiplying factor is selected as R.sub.1 =2-B.sub.o =1+q.sup.2 then B.sub.1 =B.sub.o .times.R.sub.1 =1-q.sup.4. In general, at the i.sup.th iteration, R.sub.i =1+q.sup.2.spsp.i and B.sub.i =1-q.sup.2.spsp.i+1. Since .vertline.q.vertline.&lt;1 and q.sup.2.spsp.i+1 &lt;.epsilon., B.sub.i is an approximated unity where .epsilon. represents the least significant bit of the division register in computer. Thus, AR.sub.o R.sub.1 R.sub.2 . . . R.sub.i is the desired quotient. The first multiplier R.sub.o, determined by table-lookup, is 10 bits long and yields a minimum 0 or 1 string length of seven bits in B.sub.o, namely 0.1111111xxx . . . or 0.0000000xxx . . . where x is 0 or 1.
This technique is essentially an power series evaluation of 1/B: EQU 1/B=1/(1+q)D=(1-q)(1+q.sup.2)(1+q.sup.4)(1+q.sup.8)(1+q.sup.16)(1+q.sup.32) . . . /D
where B=(1+q)D and 0&lt;q.ltoreq.1/(D-1). For 56-bits fraction, five multiplying factors, R.sub.o, R.sub.1, R.sub.2, R.sub.3, and R.sub.4 (=1+q.sup.2.spsp.i for i=1,2,3,4), are needed.
The acceleration method described in the related application was proposed to obtain a smaller value q from a given divisor. Then, the power series evaluation can be accomplished with a fewer number of multiplying factors with the smaller value where .vertline.q.vertline..ltoreq.1/(2D-3) was guaranteed. In the acceleration method, three successive applications of acceleration constants are needed in order to obtain the smaller value q.